package main

import (
	"fmt"
	"math/rand"
	"time"
)

func main() {
	array := []int{2, 3, 8, 7, 1, 2, 2, 2, 7, 3, 9, 8, 2, 1, 4}
	QuickSort(array)
	fmt.Println(array)
}

func QuickSort(array []int) {
	rand.Seed(time.Now().Unix())
	quickSort(array, 0, len(array)-1)
}

func quickSort(array []int, left, right int) {
	if left < right {
		randIdx := rand.Int() % (right - left + 1)
		swap(array, left, left+randIdx)
		partitionIndex := partition(array, left, right)
		quickSort(array, left, partitionIndex-1)
		quickSort(array, partitionIndex+1, right)
	}
}

func swap(array []int, i, j int) {
	array[i], array[j] = array[j], array[i]
}

/**
 划分
	以下标为left的元素为pivot, 在[left, right]范围内，使
	比pivot小的元素在pivot左边
	比pivot大的元素在pivot右边
*/
func partition(array []int, left, right int) int {
	pivot := array[left]
	for left < right {
		for left < right && array[right] > pivot {
			right--
		}
		if left < right {
			array[left] = array[right]
		}
		for left < right && array[left] <= pivot {
			left++
		}
		if left < right {
			array[right] = array[left]
		}
	}
	array[left] = pivot
	return left
}
